package leetcode_core.leetcode_6;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月31日 23:11
 */
public class Quick {

    public static void sort(int[] nums){
        shuffle(nums);
        sort(nums,0,nums.length-1);
    }

    public static void sort(int[] nums,int lo,int hi){
        if(lo >= hi){
            return;
        }
        //前序
        int p = partition(nums,lo,hi);
        sort(nums,lo,p-1);
        sort(nums,p+1,hi);
    }

    //对[lo,hi]进行划分
    private static int partition(int[] nums,int lo,int hi){
        int pivot = nums[lo];
        int i = lo+1;
        int j = hi;
        //使得[lo,i)<=pivot,(j,hi]>pivot
        while(i <= j){
            while (i<hi && nums[i] <= pivot){
                i++;
            }
            while (j>lo && nums[j]>pivot){
                j--;
            }
            if(i>=j){
                break;
            }
            swap(nums,i,j);
        }
        swap(nums,lo,j);
        return j;
    }

    //洗牌算法
    private static void shuffle(int[] nums){
        Random rand = new Random();
        int n = nums.length;
        for(int i = 0;i<n;i++){
            //生成从`[i,n-1]`之间的随机数
            int r = i + rand.nextInt(n-i);
            swap(nums,i,r);
        }
    }

    private static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = nums[i];
        Map<Integer,Integer> map = new HashMap<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() +" "+ entry.getValue());
        }
    }
}
